A portion of the disclosure of this patent document contains material to which a claim of copyright protection is made. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but reserves all other rights whatsoever.
This invention relates generally to the field of digital data processing apparatus and more specifically to a computer for performing a discrete transform on input data.
The Fourier transform has been well know to mathematicians, scientists, engineers and others for many years. The Fourier transform is a tool used in many fields such as medicine, economics, and engineering to analyze data.
For example, when the input data represents time-varying electrical signals, the Fourier transform is often performed to identify the frequency components within the electrical signals. Similarly, an inverse Fourier transform is often performed to produce a time-varying electrical signal from frequency components. In addition, data may be processed by first performing the Fourier transform, modifying the frequency components in a desired way, and inverting the transform.
For general background, reference is made to the book "The Fourier Transform and its Applications" McGraw-Hill, Inc., 2nd Ed. 1978 by Ronald N. Bracewell.
In digital data processing apparatus, the Fourier transform is normally performed with discrete values of input data in accordance with the well-known discrete Fourier transform (DFT) defined as follows: ##EQU2##
The inverse Fourier transform is performed by substituting "i" for "-i" in the discrete Fourier transform. In the DFT transform, N values of the input data x(n) [where n is equal to 0, 1, . . . , (N-1)] are transformed to produce N values of output data X(k), where k is equal to 0, 1, . . . , (N-1). The number N of values of input data may vary, but the larger the value of N the greater the resolution of the output data. Transforms in accordance with the above equation are called N-point or N-length DFT's . In order to practically and efficiently perform N-length DFT's, digital computers are utilized. Even using digital computers, however, performance of N-length DFT's for large N is still a formidable task. For this reason, many prior art techniques have been developed to more efficiently perform the N-length discrete Fourier transform.
One significant technique for improving the efficiency of performing the discrete Fourier transform is described in the article by J. W. Cooley and J. W. Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series", Math of Computation, Vol. 19, pp. 297-301, April 1965. When the Cooley-Tukey algorithm was utilized on a general purpose computer, a more than fifty times improvement in processing time occurred for 1024-point DFT. The Cooley-Tukey algorithm is known as the fast Fourier transform (FFT) and is a radix-2 algorithm.
General background information concerning the fast Fourier transform (FFT) and variations thereof are described in the article "What is the Fast Fourier Transform?", Proceedings of the IEEE, Vol 55, No. 10, October 1967, Cochran et. al., pp. 1664-1674. The FFT method of computing the N-length DFT relies upon selecting the transform length N as a power of 2. The calculations are grouped in pairs to achieve a significant reduction in the calculation time required for the N-length DFT.
Many other algorithms have been proposed for more efficiently performing the N-length DFT. A number of such algorithms, including the nested Winograd algorithm, are described and compared in the article "A Prime Factor FFT Algorithm Using A High-Speed Convolution" by Kolba and Parks, IEEE Transactions on Acoustics Speech and Signal Processing, Vol ASSP-25, No. 4, August 1977, pp. 281-294. In the prime factor FFT by Kolba and Parks, the transform length N is selected equal to the product of a number of mutually prime factors N.sub.1, N.sub.2, . . . , N.sub.i, . . . , N.sub.L. Each of the prime factors N.sub.i of N is employed in an N.sub.i -length DFT using convolution. In the Kolba and Parks prime factor FFT, L different and shorter length DFT's are executed in order to achieve the N-point DFT. The Kolba and Parks prime factor FFT compares favorably with the radix-2 algorithm of Cooley-Tukey and the nested algorithm of Winograd (U.S. Pat. No. 4,156,920).
While various techniques, such as those described above, have significantly improved the efficiency of performing the N-length discrete Fourier transform (DFT), even greater increases in efficiency are desirable.
The discrete Fourier transform (DFT) has two characteristics that are sometimes computationally undesirable. The inverse DFT is not identical with the direct DFT transform and so it is necessary to keep track of the +i and -i versions. Also, the DFT has complex rather than real values and thus requires provision for complex arithmetic and separately managed storage for real and imaginary parts. In many applications, both real and imaginary parts are not required and hence the calculations using both tend to be inefficient.
More efficient acquisition of complex Fourier coefficients is possible in the case of real data by a modification of the FFT algorithm. Conversely, complex inputs may be handled more efficiently, in the cases where it is known that the results should be real, by a different modified algorithm. Both of these modifications, derived from the FFT, must occupy storage space in computer memory when real data are to be processed by (i) transformation followed by (ii) operations carried out in the transform domain, and (iii) retransformation into the data domain.
While other linear integral transforms have been proposed, none heretofore have been implementable as discrete transforms suitable for use as improvements over the Discrete Fourier Transform. For example, as referred to by Bracewell, The Fourier Transform and its Applications, on page 179, Hartley is credited with linear integral transforms (Hartley Transforms), but these have not been available as discrete transforms nor have algorithms been available to implement them.
In view of the above background of the invention, there is a need for economical computers and methods for more efficiently performing and inverting N-point discrete transforms and particularly for computers which avoid unneeded complex computations when only real computations are desired.